Searching a graph of combinatorial possibilities is a general optimization technique used in various fields including artificial intelligence and operations research, among many others. There are many practical applications of these types of techniques to allow for improved performance in industry. Breadth-first search and depth-first searches are two basic search strategies upon which numerous search algorithms are built.
While the presently described embodiments disclosed in this application are not limited to a particular graph search problem, we use treewidth as a concrete example as a problem with a large encoding size and show how an embodiment of these presently described embodiments can be used to solve the treewidth problem more efficiently. To explain, by way of background, a treewidth (also known as the induced treewidth) measures how similar a graph is to a tree, which has a treewidth of 1. A graph of k vertices is least similar to a tree, if it is a completely connected graph, which has a treewidth of k−1. However, most graphs have a treewidth that is somewhere in between 1 and the number of vertices minus 1. To determine the treewidth of a graph, all vertices must be eliminated from the graph one after another until the graph is empty. When a vertex is eliminated, an edge is added to every pair of its neighbors that are not adjacent, and all the edges incident to the vertex are removed along with it. For each elimination order, the maximum degree (i.e., the number of neighbors) of any vertex when it is eliminated from graph is defined as the width of the elimination order. The treewidth of a graph is defined as the minimum width over all possible elimination orders, and an optimal elimination order is any order whose width is the same as the treewidth.
The treewidth of a graph plays a central role in determining the complexities of many algorithms based on graphical models. For example, the complexities of Bayesian-network algorithms such as Bucket Elimination, JoinTree, and Recursive Conditioning are all exponential in the treewidth of the underlying graph induced by the network. Thus, reducing the treewidth even by a small amount can result in huge computational savings for various probabilistic inferences over Bayesian networks.
Some previous work used depth-first search to find optimal treewidth by searching in the space of all possible vertex elimination orders. Depth-first search provides the advantage of excellent memory-reference locality and thus increased execution speed. On the other hand, depth-first search is most effective for problems with a tree structure, but unfortunately the treewidth problem, as well as many other important combinatorial problems, has a graph structure with many alternative paths between nodes in the search space. Although in theory it is always possible to “unroll” a search graph into a search tree, doing so often results in an exponential increase in the size of the search space and in practice depth-first search is often found to be unacceptably slow on a wide range of graph-search problems, due to the extraordinary number of duplicate search nodes that it has to deal with.
Recently, P. Alex Dow and Rich Korf, Best-first Search for Treewidth, Proceedings of the 22d National Conference on Artificial Intelligence (AAAI-07), pages 1146-1151 (2007) (hereinafter referred to as Dow and Korf [AAAI-07]), which is incorporated herein by reference in its entirety, have shown breadth-first and best-first search can dramatically outperform depth-first search by avoiding repeated generation of duplicate search nodes. The difficulty with a breadth/best-first search, however, is memory requirements, which tend to grow exponentially with the size of the graph. To compute the treewidth, each node in the search space represents an intermediate graph resulted from eliminating a subset of vertices from the original graph. Since the size of an intermediate graph can vary from several kilobytes to a few megabytes, storing the entire intermediate graph at each node is impractical for all but the smallest problem. To improve memory efficiency, Dow and Korf propose to store only the set of vertices that have been eliminated so far (as opposed to the intermediate graph) at each node. Every time a node is expanded, its corresponding intermediate graph is reconstructed by eliminating from the original graph those vertices stored with the node. Note that the original graph only needs to be stored once globally. While being space-efficient, this approach incurs the overhead of intermediate graph reconstruction every time a node is expanded. For large graphs, such overhead can be quite significant. This detracts from the advantages provided by breadth-first search.